﻿#include <iostream>

#define MIN(a, b) (a < b ? a : b)

static int totalWaterCapacity(const int* blocks, const size_t blockArrSize)
{
    if (blockArrSize < 3) return 0;

    int max = 0;
    int maxIndex = 0;
    for (int i = 0; i < blockArrSize; i++)
    {
        if (max < blocks[i])
        {
            max = blocks[i];
            maxIndex = i;
        }
    }

    int* waterArr = (int*)malloc(sizeof(int) * blockArrSize);
    memset(waterArr, 0, sizeof(int) * blockArrSize);

    int lMax = blocks[0];
    int rMax = blocks[blockArrSize - 1];
    int lIndex = 1;
    int rIndex = blockArrSize - 2;
    while (lIndex <= rIndex)
    {
        if (lIndex < maxIndex)
        {
            if (blocks[lIndex] > lMax)
            {
                lMax = blocks[lIndex];
            }
            else
            {
                waterArr[lIndex] = abs(MIN(lMax, max) - blocks[lIndex]);
            }

            ++lIndex;
        }

        if (rIndex > maxIndex)
        {
            if (blocks[rIndex] > rMax)
            {
                rMax = blocks[rIndex];
            }
            else
            {
                waterArr[rIndex] = abs(MIN(rMax, max) - blocks[rIndex]);
            }

            --rIndex;
        }

        if (lIndex == maxIndex && rIndex == maxIndex) break;
    }

    int total = 0;
    for (int i = 1; i < blockArrSize - 1; i++)
    {
        total += waterArr[i];
    }

    return total;
}

/**
 * 给定一个数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，
 * 请返回容器能装多少水。
 * 比如, arr=[3,1,2,5,2,4], 根据值画出的直方图就是容器形状，该容器可以装下5格水。
 *
 *      口
 *      口水口
 * 口水水口水口
 * 口水口口口口
 * 口口口口口口
 * 3 1 2 5 2 4
 *
 * 再比如，arr=[4,5,1,3,2], 该容器可以装下2格水
 *
 *  口
 * 口口
 * 口口水口
 * 口口水口口
 * 口口口口口
 * 4 5 1 3 2
 *
 * 思路：
 * 第i个位置能盛多少水，是由arr的0->i-1位置的最大值和arr的i+1->N-1位置的最大值决定的，即
 * i位置能盛水的数量=min(Max(left), Max(right))-arr[i]。
 * 如果arr[i]比上一步的最小值都大或者相等，则无法盛水。
 *
 * 把每个位置能盛的水求和，就是总共能盛多少水。
 */
int main_WaterCapacity()
{
    int blocks[] = { 30,1,99,2,5 };
    auto size = sizeof(blocks) / sizeof(int);
    int waterCapacity = totalWaterCapacity(blocks, size);
    printf("%d", waterCapacity);
    return 0;
}